<!DOCTYPE html>
<html lang="zh-cn" itemscope itemtype="http://schema.org/WebPage">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <title>友知弄</title>
  

<meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta name="MobileOptimized" content="width"/>
<meta name="HandheldFriendly" content="true"/>


<meta name="applicable-device" content="pc,mobile">

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">

<meta name="mobile-web-app-capable" content="yes">

<meta name="author" content="yixy" />
  <meta name="description" content="YOUZHILANE" />
  <meta name="keywords" content="essay, notes" />






<meta name="generator" content="Hugo 0.56.1" />


<link rel="canonical" href="https://yixy.github.io/youzhilane/" />
<link href="%7balternate%20%7bRSS%20application/rss&#43;xml%20%20index%20alternate%20%20false%20false%20true%20false%20false%200%7d%20/youzhilane/index.xml%20https://yixy.github.io/youzhilane/index.xml%7d" rel="alternate" type="application/rss+xml" title="友知弄" />



<link rel="icon" href="/youzhilane/favicon.ico" />











<link rel="stylesheet" href="/youzhilane/sass/jane.min.af20b78e95c84de86b00a0242a4a77bd2601700e1b250edf27537d957ac0041d.css" integrity="sha256-ryC3jpXITehrAKAkKkp3vSYBcA4bJQ7fJ1N9lXrABB0=" media="screen" crossorigin="anonymous">





<meta property="og:title" content="友知弄" />
<meta property="og:description" content="YOUZHILANE" />
<meta property="og:type" content="website" />
<meta property="og:url" content="https://yixy.github.io/youzhilane/" />

<meta property="og:updated_time" content="2019-11-17T00:22:22+08:00" />
<meta itemprop="name" content="友知弄">
<meta itemprop="description" content="YOUZHILANE">

<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="友知弄"/>
<meta name="twitter:description" content="YOUZHILANE"/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->




</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/youzhilane/" class="logo">友知弄</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          
        
      </li><li class="mobile-menu-item">
        
          
          <div class="mobile-menu-parent">
            <span class="mobile-submenu-open"></span>
            <a href="https://yixy.github.io/youzhilane/post/">
              归档
            </a>
          </div>
          <ul class="mobile-submenu-list">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>
        
      </li>
    

    
  </ul>
</nav>


  
    






  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/photoswipe.min.css" />
  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/default-skin/default-skin.min.css" />




<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

<div class="pswp__bg"></div>

<div class="pswp__scroll-wrap">
    
    <div class="pswp__container">
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
    </div>
    
    <div class="pswp__ui pswp__ui--hidden">
    <div class="pswp__top-bar">
      
      <div class="pswp__counter"></div>
      <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
      <button class="pswp__button pswp__button--share" title="Share"></button>
      <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
      <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
      
      
      <div class="pswp__preloader">
        <div class="pswp__preloader__icn">
          <div class="pswp__preloader__cut">
            <div class="pswp__preloader__donut"></div>
          </div>
        </div>
      </div>
    </div>
    <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
      <div class="pswp__share-tooltip"></div>
    </div>
    <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
    </button>
    <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
    </button>
    <div class="pswp__caption">
      <div class="pswp__caption__center"></div>
    </div>
    </div>
    </div>
</div>

  

  

  

  <header id="header" class="header container">
    <div class="logo-wrapper">
  <a href="/youzhilane/" class="logo">
    
      友知弄
    
  </a>
</div>

<nav class="site-navbar">
  <ul id="menu" class="menu">
    
    
        <li class="menu-item active">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          <a class="menu-item-link menu-parent" href="https://yixy.github.io/youzhilane/post/">归档</a>
          <ul class="submenu">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>

        

      </li>
    

    
    

    
  </ul>
</nav>

  </header>

  <div id="mobile-panel">
    <main id="main" class="main bg-llight">
      <div class="content-wrapper">
        <div id="content" class="content container">
          
<section id="posts" class="posts">
  
  
    
  
  
  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/06%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84huffman%E6%A0%91/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 19 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
       基础数据结构——Huffman树 1. Huffman树 首先给出路径和路径长度的概念。
 路径：路径是指在一棵树中，从一个节点到另一个节点之间的分支构成的通路。 路径长度：路径长度指的是路径上分支的数目。 树的路径长度：指从树根到每个叶子结点的路径长度之和。 结点的带权路径长度：从该结点到树根之间路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。  给定n权值作为n个叶子节点，构造一棵二叉树，若这棵二叉树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为Huffman树。
2. 构造Huffman树 Huffman树的构建步骤如下
 将给定的n个权值看做n棵只有根节点（无左右孩子）的二叉树，组成一个集合HT，每棵树的权值为该节点的权值。 从集合HT中选出2棵权值最小的二叉树，组成一棵新的二叉树，其权值为这2棵二叉树的权值之和。 将步骤2中选出的2棵二叉树从集合HT中删去，同时将步骤2中新得到的二叉树加入到集合HT中。 重复步骤2和步骤3，直到集合HT中只含一棵树，这棵树便是赫夫曼树。  3. Huffman编码 
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/06%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84huffman%E6%A0%91/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/07%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9B%BE/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 29 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
       基础数据结构——图 1. 基础概念  图（Graph）是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为： G(V,E)。其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。  需要注意的是，图中数据元素叫做顶点（Vertext）。在图中，不允许没有顶点。若 V 是图的顶点的集合，那么，V 是非空有穷集合。图的任意两个顶点之间都可能有关系，它们的关系用边来表示。边集可以是空的。
 无向边：若顶点之间的边没有方向，这条边就叫做无向边（Edge）,用无序偶对 (i,j) 来表示。 无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无项图（Undirected graphs）。 有向边：若从顶点i到j的边有方向，则称这条边为有向边，也称为弧 (Arc)。这条有向边用有序偶 &lt;i,j&gt;来表示，j是弧尾(Tail)，i是弧头(Head)。 有向图：如果图中任意两个顶点之间的边都是有向边，这个图就是有向图。 无向完全图：在无向图中，如何任意两点之间都存在边，这个图就是无向完全图。 有向完全图：在有向图中，如果任意两点之间都存在方向互为相反的两条弧，这个图就是有向完全图。 权：与图的边或弧相关的数字叫做权（Weight）。权可以表示一个顶点到另一个顶点的距离或耗费。 网：带权的图叫做网（Network）。  
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/07%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9B%BE/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/08%E6%9F%A5%E6%89%BE/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 111 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      查找 1. 什么是查找  查找：事先给定一个值，在查找表（同一类型的数据元素构成的集合）中找到其关键字等于给定值的数据元素（一个或多个）。  除了时间复杂度和空间复杂度之外，通常还使用ASL来衡量查找算法的好坏程度。
 平均查找长度ASL（Average Search Length）：关键字的平均比较次数。  2. 静态查找与动态查找 查找的目的：
 查询特定数据是否在查找表中 检索查找表中某个特定数据的属性 在查找表中插入一个数据元素 在查找表中删除某个数据元素   静态查找（static search）：仅对查找表进行上述的前两种查找操作 动态查找（dynamic search）：存在上述的第3种或第4种查找操作  3. 查找相关的数据结构对比  线性表：线性表中效率最好的二分查找为O(logn)，但是对动态查找支持不好（要求有序并且是顺序表，插入删除操作需要大量元素移动）  线性表的顺序查找适用场景较广，但是效率相对较低。若是动态查找场景，可以采用链表实现，避免大量元素移动；并且由于线性表中元素无序，所以即使是采用顺序存储，新增时也不会产生大量元素移动。
 时间复杂度：O(n) 空间复杂度：O(1)  线性表的二分查找效率较好，但是适用场景单一（要求有序并且是顺序表），对于动态查找场景（大量插入和删除）需要移动大量元素。
 时间复杂度：O(logn) 空间复杂度：O(1)，非递归实现  线性表分块索引查找性能介于顺序查找和二分查找之间。对于动态查找场景，插入、删除较为容易，无需进行大量元素移动。但需要引入额外的索引存储空间，并对初始索引进行排序计算。
 时间复杂度：log(n/s) + s，s为每块元素数量 空间复杂度：O(n/s)   平衡二叉树（AVL）与红黑树：如果希望拥有与折半查找同样的查找效率O(logn)，并且对频繁的插入删除操作不需要大量元素移动，可以使用AVL或红黑树。   二叉排序树：时间复杂度最佳情况是 O(log­n)，而最坏情况是 O(n)。空间复杂度是O(n)，因为有指针。 AVL：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及平衡因子。 RBtree：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及颜色标记。  二叉查找树最坏查找次数是树的深度。其平均查找长度与树的形态有关，树的高度越高，平均查找长度越长，最佳情况是 O(log­2n)——树比较平衡的状态，而最坏情况是 O(n)——即退化成为线性顺序查找。
 AVL树：一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。 红黑树：通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。  AVL是一种高度平衡的二叉树，所以通常的结果是，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。红黑树平衡度没AVL那么好。也就是说，如果从高度差来说，红黑树是大于AVL的，其实也就代表着它的实际查询时间(最坏情况)略逊于AVL的。数学证明红黑树的最大深度是 2log(2n+1), 其实最差情况它从根到叶子的最长路可以是最短路的两倍，但也不是很差，所以它的查询时间复杂度也是O（log n）。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/08%E6%9F%A5%E6%89%BE/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/09%E7%BA%BF%E6%80%A7%E8%A1%A8%E6%9F%A5%E6%89%BE%E9%A1%BA%E5%BA%8F%E6%9F%A5%E6%89%BE/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 8 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      线性表查找——顺序查找 按顺序对查找表中数据进行逐个查找，若匹配成功则返回查找记录查找成功，若无可匹配记录则查找失败。
 可以设置哨兵来提高顺序查找性能，避免查找过程中每一步都要检测整个表是否查找完毕的操作。
  等概率情况下：ASL=(n+1)/2 适用存储结构：顺序表或链表 不要求查找表有序 空间复杂度：O(1)  线性表的顺序查找适用场景较广，但是效率相对较低。若是动态查找场景，可以采用链表实现，避免大量元素移动；并且由于线性表中元素无序，所以即使是采用顺序存储，新增时也不会产生大量元素移动。
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/09%E7%BA%BF%E6%80%A7%E8%A1%A8%E6%9F%A5%E6%89%BE%E9%A1%BA%E5%BA%8F%E6%9F%A5%E6%89%BE/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/10%E7%BA%BF%E6%80%A7%E8%A1%A8%E6%9F%A5%E6%89%BE%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 10 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      线性表查找——二分查找 在有序的情况下，先确定待查记录所在区间，然后逐步缩小范围直到找到活找不到该记录为止。
 以下log表示以2为底的对数
  等概率情况下：ASL=[(n+1)/n] * log(n+1)-1 适用存储结构：顺序表。（因为需要能够随机定位到中间的下标） 要求查找表有序 空间复杂度：O(1)  线性表的二分查找效率较好，但是适用场景单一（要求有序并且是顺序表），对于动态查找场景（大量插入和删除）需要移动大量元素。
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/10%E7%BA%BF%E6%80%A7%E8%A1%A8%E6%9F%A5%E6%89%BE%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
</section>






  
  
  

  
  

  
  

  
  

  
  

    <nav class="pagination">
      <ul>

      
      
      <li><a href="/youzhilane/">««</a></li>
      

      
      
      <li><a href="/youzhilane/page/9/">«</a></li>
      

      
      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/4/">
              4
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/5/">
              5
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/6/">
              6
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/7/">
              7
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/8/">
              8
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/9/">
              9
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="active">
            <a href="/youzhilane/page/10/">
              10
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/11/">
              11
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/12/">
              12
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/13/">
              13
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/14/">
              14
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/15/">
              15
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/16/">
              16
            </a>
          </li>
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

      
      
      <li><a href="/youzhilane/page/11/">»</a></li>
      

      
      
      <li><a href="/youzhilane/page/19/">»»</a></li>
      

      </ul>
    </nav>
  





        </div>
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="icon-links">
  
  
    <a href="mailto:youzhilane01@gmail.com" rel="me noopener" class="iconfont"
      title="email" >
      <svg class="icon" viewBox="0 0 1451 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="36" height="36">
  <path d="M664.781909 681.472759 0 97.881301C0 3.997201 71.046997 0 71.046997 0L474.477909 0 961.649408 0 1361.641813 0C1361.641813 0 1432.688811 3.997201 1432.688811 97.881301L771.345323 681.472759C771.345323 681.472759 764.482731 685.154773 753.594283 688.65053L753.594283 688.664858C741.602731 693.493018 729.424896 695.068979 718.077952 694.839748 706.731093 695.068979 694.553173 693.493018 682.561621 688.664858L682.561621 688.65053C671.644501 685.140446 664.781909 681.472759 664.781909 681.472759L664.781909 681.472759ZM718.063616 811.603883C693.779541 811.016482 658.879232 802.205449 619.10784 767.734955 542.989056 701.759633 0 212.052267 0 212.052267L0 942.809523C0 942.809523 0 1024 83.726336 1024L682.532949 1024 753.579947 1024 1348.948139 1024C1432.688811 1024 1432.688811 942.809523 1432.688811 942.809523L1432.688811 212.052267C1432.688811 212.052267 893.138176 701.759633 817.019477 767.734955 777.248 802.205449 742.347691 811.03081 718.063616 811.603883L718.063616 811.603883Z"></path>
</svg>

    </a>


<a href="https://yixy.github.io/youzhilane/index.xml" rel="noopener alternate" type="application/rss&#43;xml"
    class="iconfont" title="rss" target="_blank">
    <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="30" height="30">
  <path d="M819.157333 1024C819.157333 574.592 449.408 204.8 0 204.8V0c561.706667 0 1024 462.293333 1024 1024h-204.842667zM140.416 743.04a140.8 140.8 0 0 1 140.501333 140.586667A140.928 140.928 0 0 1 140.074667 1024C62.72 1024 0 961.109333 0 883.626667s62.933333-140.544 140.416-140.586667zM678.784 1024h-199.04c0-263.210667-216.533333-479.786667-479.744-479.786667V345.173333c372.352 0 678.784 306.517333 678.784 678.826667z"></path>
</svg>

  </a>
   
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - <a class="theme-link" href="https://github.com/xianmin/hugo-theme-jane">Jane</a>
  </span>

  <span class="copyright-year">
    &copy;
    2019
    <span class="heart">
      
      <i class="iconfont">
        <svg class="icon" viewBox="0 0 1025 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="14" height="14">
  <path d="M1000.1 247.9c-15.5-37.3-37.6-70.6-65.7-98.9-54.4-54.8-125.8-85-201-85-85.7 0-166 39-221.4 107.4C456.6 103 376.3 64 290.6 64c-75.1 0-146.5 30.4-201.1 85.6-28.2 28.5-50.4 61.9-65.8 99.3-16 38.8-24 79.9-23.6 122.2 0.7 91.7 40.1 177.2 108.1 234.8 3.1 2.6 6 5.1 8.9 7.8 14.9 13.4 58 52.8 112.6 102.7 93.5 85.5 209.9 191.9 257.5 234.2 7 6.1 15.8 9.5 24.9 9.5 9.2 0 18.1-3.4 24.9-9.5 34.5-30.7 105.8-95.9 181.4-165 74.2-67.8 150.9-138 195.8-178.2 69.5-57.9 109.6-144.4 109.9-237.3 0.1-42.5-8-83.6-24-122.2z"
   fill="#8a8a8a"></path>
</svg>

      </i>
    </span><span class="author">
        yixy
        
      </span></span>

  
  

  
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont">
        
        <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="35" height="35">
  <path d="M510.866688 227.694839 95.449397 629.218702l235.761562 0-2.057869 328.796468 362.40389 0L691.55698 628.188232l241.942331-3.089361L510.866688 227.694839zM63.840492 63.962777l894.052392 0 0 131.813095L63.840492 195.775872 63.840492 63.962777 63.840492 63.962777zM63.840492 63.962777"></path>
</svg>

      </i>
    </div>
  </div>
  
<script type="text/javascript" src="/youzhilane/lib/jquery/jquery-3.2.1.min.js"></script>
  <script type="text/javascript" src="/youzhilane/lib/slideout/slideout-1.0.1.min.js"></script>




<script type="text/javascript" src="/youzhilane/js/main.638251f4230630f0335d8c6748e53a96f94b72670920b60c09a56fdc8bece214.js" integrity="sha256-Y4JR9CMGMPAzXYxnSOU6lvlLcmcJILYMCaVv3Ivs4hQ=" crossorigin="anonymous"></script>












  
    <script type="text/javascript" src="/youzhilane/js/load-photoswipe.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe.min.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe-ui-default.min.js"></script>
  















</body>
</html>
